The present invention relates to the field of communications in asynchronous transfer mode (ATM). It relates more particularly to the use of reverse Omega networks in ATM type binary data packet (or cell) switches. ATM techniques are envisaged for broadband integrated services networks, the data borne by the cells possibly representing audio or video data, computer data or the like.
"Information bits of the cells" is understood herein to mean both the bits representing the user information and those representing the network information (headers of the ATM cells).
A reverse Omega network with 2.sup.N inputs and L stages (L.ltoreq.N) consists of a matrix of 2.sup.N -1 rows and L columns of binary switching elements, with two inputs and two outputs, interconnected according to the following law (assuming the inputs and outputs of each column to be numbered from i=0 to i=2.sup.N -1 from the bottom to the top of the column):
the 2.sup.N inputs of column 0 constitute the 2.sup.N ordered inputs of the network; PA1 output i of column j-1 is connected to the input Rrot(i) of column j, for 0.ltoreq.i.ltoreq.2.sup.N -1 and 1.ltoreq.j.ltoreq.L-1; PA1 output i of column L-1 constitutes the output Rrot(i) of the network, for 0.ltoreq.i.ltoreq.2.sup.N -1; PA1 i lying between 0 and 2N-1 is represented by N bits with base 2, and the notation Rrot(i) used above denotes the number lying between 0 and 2N-1 whose binary representation corresponds to the N bits representing i, subjected to a circular permutation of one position to the right. For example with N=5 and i=25=[11001].sub.2, we have Rrot(i)=[11100]2.sub.2 =28. Each stage of the reverse Omega network consists of a column of 2.sup.N-1 binary switching elements and of the interconnection pattern situated downstream towards the next column. PA1 a state register of 2.sup.N bits, having a serial shift mode and a parallel transfer mode in which it receives 2.sup.N state bits each indicating whether the cell destined for one of the 2.sup.N inputs of the network is free or occupied; PA1 a first counter on L bits, incremented by one unit when a state bit obtained from the serial output of the state register in serial shift mode indicates an occupied cell; PA1 a second counter on L bits, decremented by one unit when the state bit obtained from the serial output of the state register in serial shift mode indicates a free cell; PA1 addressing registers of 2.sup.N bits each, having a serial shift mode and a parallel transfer mode, cascaded so that the (i+1)-th addressing register receives the contents of the i-th addressing register in parallel transfer mode for 1.ltoreq.i&lt;L; and PA1 a multiplexer having L output bits addressed respectively to the serial inputs of the L addressing registers, a first L-bit input connected to the output of the first counter on L bits and selected when the state bit obtained from the serial output of the state register in serial shift mode indicates an occupied cell, and a second L-bit input connected to the output of the second counter on L bits and selected when the state bit obtained from the serial output of the state register in serial shift mode indicates a free cell,
The binary switching element 15 is for example in accordance with the diagram of FIG. 1. The lower input IN0 and upper input IN1 are each connected to an input of two respective AND gates 16,17 and 18,19. An OR gate 20 has two inputs connected respectively to the outputs of the AND gates 16 and 18 and an output constituting the lower output SS0 of the element 15. An OR gate 21 has two inputs connected respectively to the outputs of the AND gates 17 and 19, and an output constituting the upper output SS1 of the element 15. The element 15 furthermore includes a D flip-flop 22 clocked by a signal Hg, whose D input is connected to the upper input IN1 of the element 15. The second inputs of the AND gates 16 and 19 are each connected to the Q output of the flip-flop 22, and the second inputs of the AND gates 17 and 18 are each connected to the inverted output Qof the flip-flop 22.
By way of example, FIG. 2 shows a switching fabric consisting of a reverse Omega network 24 with 32 inputs and 5 stages (N=L=5) composed of binary switching elements 15 of the type illustrated in FIG. 1. FIG. 3 shows a switching fabric comprising a reverse Omega network 25 with 32 inputs and 4 stages (N=5,L=4) supplemented with a concentration stage 26. FIG. 4 shows a switching fabric comprising a reverse Omega network 28 with 32 inputs and 2 stages (N=5,L=2) supplemented with three successive concentration stages 29, 30 and 31. In the fabrics of FIGS. 3 and 4, where there are N-L successive concentration stages each having a concentration ratio of 2/1 (so that the overall fabric has 2.sup.N inputs and 2.sup.L outputs), the k-th concentration stage is composed of 2.sup.N-k OR gates 33 arranged columnwise. Each OR gate 33 has two inputs connected respectively to two consecutive outputs of the preceding stage (concentration stage or last stage of the reverse Omega network). In other words, the output i of the k-th concentration stage (1.ltoreq.k .ltoreq.N-L and 0.ltoreq.i.ltoreq.2.sup.N-k- 1) is provided by an OR gate 33 whose two inputs are connected to the outputs 2i and 2i+1 of the preceding stage.
Each data cell arriving at an input of a fabric of the type illustrated in FIG. 2, 3 or 4 includes a header of L bits at least, the (j+1)-th bit b(j) of the header (0.ltoreq.j.ltoreq.L-1) being intended to control the switching in the binary switching elements of column j of the reverse Omega network, by routing the cell to the upper output SS1 when b(j)=1 and to the lower output SS0 when b(j)=0. This switching is achieved by sending to the elements 15 of column j a clocking signal Hg adjusted so as to allow storage of the bit b(j) in the flip-flop 22 over the duration of transit of a cell. A priori, a conflict may therefore occur in a binary switching element 15 if two cells arrive simultaneously on its two inputs IN0 and IN1 with identical routing bits b(j).
It is desirable to generate the routing bits b(j) for the various cells in such a way as to avoid such conflicts arising.
The reverse Omega networks have the property of being self-routing. In the case of FIG. 2, where N=L, this means that the routing bits b(N-1) . . . , b(1),b(0) included within the header of each cell and considered in the inverse order of the columns are the binary representation of the output address, that is to say of the number of that output of the reverse Omega network to which the cell will be routed. This self-routing property is generalizable to the case where L &lt;N and where the L stages of the reverse Omega network are followed by N-L concentration stages such as represented in FIGS. 3 and 4 : the L routing bits b(L-1), . . . ,b(0) are then likewise the binary representation of the output address, that is to say of the number of that output of the overall fabric to which the cell will be routed.
A routing algorithm which eliminates conflicts in a switching fabric such as represented in FIG. 2, 3 or 4 has been set out in the document FR-A-2 678 794. In the brief discussion of the routing algorithm which follows and throughout the specification, the terms "free" or "empty" cells and "occupied" cells are used. These terms are interchangeable with other similar terms of art such as "idle" (for "free" or "empty") and "active" or "busy" (for "occupied"). The terms "unmarked" ("free") and "marked" ("occupied") are also used below. This algorithm consists in allocating to the free or empty cells an output address resulting from the decrementation of a first counting variable with the arrival of each free cell, and in allocating to the occupied cells an output address resulting from the incrementation of a second counting variable with the arrival of each occupied cell. This ensures a routing of the free cells in the descending circular direction of the outputs, and a routing of the occupied cells in the rising circular direction of the outputs, without any risk of conflict in the reverse Omega network. When L&lt;N it is possible that more than 2.sup.L cells may arrive simultaneously at the input, something which does not provoke any conflict in the L stages of the reverse Omega network but may provoke collisions in the OR gates of the concentration stages. To avoid such collisions, the algorithm provides for the setting to zero of any cells in excess of 2.sup.L. Such a setting to zero causes the loss of the cell, but the probability of such a loss is in general fairly low, as in the concentrators of knockout switches (see "The Knockout switch a simple, modular architecture for high-performance packet switching", Y. S. Yeh et al., IEEE Journal on Selected Areas in Communications, Vol. SAC-5, No. 8, October 1987, pages 1274-1283).
At each cell time, the above algorithm involves the calculation of 2.sup.N addresses of L bits and their insertion at the head of the 2.sup.N cells, free or occupied, which are to be addressed simultaneously to the 2.sup.N inputs of the switching fabric. Software implementation would require sequential calculations and insertions which would introduce significant cell transmission delays. The same difficulty is encountered in the case of hardware implementation.
An object of the invention is to associate a switching fabric comprising a reverse Omega network with a routing bits generator which avoids conflicts between cells without excessively delaying their transmission.